package com.berchen.test;

/**
 * 两个链表的第一个公共节点
 *
 * 链表1 公共节点前面有3个节点
 * 链表2 公共节点前面有2个节点
 *  公共链表节点有2 个
 * 将 链表1 和2 放一起 遍历
 *  链表1 完了 链表2
 *  链表2 完了 链表1
 *  当走的一定长度的时候 就走到公共节点了
 *
 * 1 -> 2 -> 3
 *             -> 6 -> 7
 *      4 -> 5
 *
 * 第一步 l1=1  l2=4
 *       l1=2  l2=5
 *       l1=3  l2=6
 *       l1=6  l2=7
 *       l1=7  l2=1 // 从这个地方 l2 开始指向 链表1 了
 *       l1=4  l2=2 // 从这个地方 l1 开始执行 链表2 了
 *       l1=5  l2=3
 *       l1=6  l2=6 // 这个时候 两个链表的第一个公共节点就找到了
 *
 */
public class TwoLinkedPub {

    public static void main(String[] args){

        ListNode pHead1=new ListNode(1);
        ListNode pHead2=new ListNode(4);
        ListNode node1=new ListNode(2);
        ListNode node2=new ListNode(3);
        ListNode node3=new ListNode(5);
        ListNode node4=new ListNode(6);
        ListNode node5=new ListNode(7);
        pHead1.next=node1;
        node1.next=node2;
        node4.next=node5;
        pHead2.next=node3;
        node3.next=node4;
        node2.next=node4;

        TwoLinkedPub twoLinkedPub = new TwoLinkedPub();
        ListNode listNode = twoLinkedPub.FindFirstCommonNode(pHead1, pHead2);
        while (listNode!=null){
            System.out.println(listNode);
            listNode=listNode.next;
        }
    }

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        ListNode l1=pHead1;
        ListNode l2=pHead2;
        while (l1!=l2){
            l1=l1==null?pHead2:l1.next;
            l2=l2==null?pHead1:l2.next;
        }
        return l1;

    }
}
